#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣42. 接雨水
// 【难度】困难
// 【提交】2025.9.15 https://leetcode.cn/problems/trapping-rain-water/submissions/663015152/
// 【标签】双指针；动态规划；单调栈
class Solution_LC42 {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 模型：双指针法，通过维护左右两侧的最大高度来计算每个位置的积水量。
 * 
 * 二、标准解法状态设计
 * 使用两个指针 left 和 right 分别从数组两端向中间移动，同时维护 leftMax 和 rightMax 分别表示
 * 左侧和右侧遇到的最大高度。对于每个位置，积水量取决于左右两侧最大高度中的较小值。
 * 
 * 三、你的实现思路
 * 使用双指针法，通过比较左右指针所指的高度，决定移动哪一侧的指针，并计算当前位置的积水量。
 * 
 * 四、逐行注释（带细节提醒）
 * int ans = 0;                    // 初始化总积水量
 * int left = 0, right = height.size() - 1;  // 初始化左右指针
 * int leftMax = 0, rightMax = 0;  // 初始化左右最大高度
 * while (left < right) {          // 当左右指针未相遇时循环
 *     leftMax = max(leftMax, height[left]);    // 更新左侧最大高度
 *     rightMax = max(rightMax, height[right]); // 更新右侧最大高度
 *     if (height[left] < height[right]) {      // 如果左侧高度较小
 *         ans += leftMax - height[left];       // 计算左侧当前位置的积水量
 *         ++left;                 // 移动左指针
 *     } else {                    // 如果右侧高度较小
 *         ans += rightMax - height[right];     // 计算右侧当前位置的积水量
 *         --right;                // 移动右指针
 *     }
 * }
 * 
 * 五、正确性证明
 * 该算法基于贪心策略，总是处理高度较小的一侧。因为积水量由较低一侧的最大高度决定，所以能保证每个位置
 * 的积水量被正确计算。左右指针向中间移动的过程中，不会漏掉任何可能的积水位置。
 * 
 * 六、复杂度
 * 时间：O(n)，只需遍历数组一次。
 * 空间：O(1)，只使用了常数级别的额外空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，只需一次遍历；
 *   - 空间复杂度低，仅使用常数空间；
 *   - 代码简洁，实现高效。
 * 缺点：
 *   - 对于初学者来说，双指针的移动策略可能不太直观；
 *   - 没有显式处理空数组或单元素数组的情况（但算法能正确处理）。
 * 
 * 八、改进建议
 * 1. 可以添加提前判断：if (height.empty()) return 0;
 * 2. 使用更明确的变量名（如 leftHeight 和 rightHeight）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释为什么移动高度较小的一侧指针。
 * 
 * 九、一句话总结
 * 双指针法是解决接雨水问题的高效方法，你的实现准确且优雅，只需稍加注释即可提升可读性。
 */